package com.cg.offer;

import org.junit.Test;

/**
 * 剑指Offer 53-I.在排序数组中查找数字 I
 *
 * @program: LeetCode->Offer_53_I
 * @description: 剑指Offer 53-I.在排序数组中查找数字 I
 * @author: cg
 * @create: 2022-03-12 16:06
 **/
public class Offer_53_I {

    @Test
    public void test53() {
        System.out.println(search(new int[]{}, 0));
        System.out.println(search(new int[]{2, 2}, 2));
        System.out.println(search(new int[]{5, 7, 7, 8, 8, 10}, 8));
        System.out.println(search(new int[]{1}, 1));
        System.out.println(search(new int[]{5, 7, 7, 8, 8, 10}, 6));
    }

    /**
     * 统计一个数字在排序数组中出现的次数。
     * <p>
     * 示例 1:
     * 输入: nums = [5,7,7,8,8,10], target = 8
     * 输出: 2
     * <p>
     * 示例 2:
     * 输入: nums = [5,7,7,8,8,10], target = 6
     * 输出: 0
     * <p>
     * 提示：
     * 0 <= nums.length <= 10的次5幂
     * -10的次9幂 <= nums[i] <= 10的次9幂
     * nums 是一个非递减数组
     * -10的次9幂 <= target <= 10的次9幂
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        // 搜索右边界 right
        int l = 0, r = nums.length - 1;
        while(l <= r) {
            int m = (l + r) / 2;
            if(nums[m] <= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        int right = l;
        // 若数组中无 target ，则提前返回
        if(r >= 0 && nums[r] != target) {
            return 0;
        }
        // 搜索左边界 right
        l = 0; r = nums.length - 1;
        while(l <= r) {
            int m = (l + r) / 2;
            if(nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        int left = r;
        return right - left - 1;
    }

}
